1. Field of the Invention
The present invention relates generally to a method for controlling execution of a data driven type information processor, and more particularly, to a method for controlling execution of data packets in a copying process.
2. Description of the Background Art
In a conventional von Neumann type computer, various instructions are stored as a program in a program memory in advance and the addresses in the program memory are sequentially designated by a program counter to sequentially read the instructions to be executed.
A data driven type information processor is one type of non-von Neumann the computers having no concept of sequential execution of instructions by a program counter. Such a data driven type information processor employs architecture based on a parallel processing of instructions. In the data driven type information processor, collection of data which are to be operated on renders an instruction executable and a plurality of instructions are simultaneously driven by the data to execute the program in a parallel manner in accordance with the natural flow of the data. As a result, a time period required for the operation is significantly reduced.
FIG. 6 is a block diagram showing one example of an arrangement of a conventional data driven type information processing device. FIG. 7 is a block diagram showing an arrangement of a program storing portion contained in the information processing device. FIG. 8 is a diagram showing one example of a filed arrangement of a data packet to be processed by the information processing device.
The data packet shown in FIG. 8 comprises a destination field, an instruction filed, a data 1 field and a data 2 field. The destination field stores destination information, the instruction field stores instruction information, and the data 1 field or the data 2 field stores operand data.
The information processing device shown in FIG. 6 comprises a program storing portion 1, a data pair generating portion 2 and an operation processing portion 3. The program storing portion 1 and the data pair generating portion 2 are coupled to each other by data transmission paths 4 and 5. The data pair generating portion 2 and the operation processing portion 3 are coupled to each other by a data transmission path 6 and the operation processing portion 3 and the program storing portion 1 are coupled to each other by a transmission path 7.
The program storing portion 1 is disclosed in more detail in U.S. application Ser. No. 07/260,045, now U.S. Pat. No. 5,093,919, filed Oct. 20, 1988.
The program storing portion 1 includes an information fetching portion 8, an input buffer 10 and an output buffer 11 as shown in FIG. 7. The input buffer 10 comprises a plurality of data latches 9a, 9b and 9c. The information fetching portion 8 has two output ports. The output buffer 11 comprises data latches 11a and 11b connected between one output port of the information fetching device 8 and the data transmission path 4 and data latches 11c and 11d connected between the other output port of the portion 8 and the data transmission path 5. The input buffer 10 and the output buffer 11 serve to transfer data packets stored in each data latch to each data latch in the subsequent stage with the lapse of time.
The information fetching portion 8 stores the data flow program shown in FIG. 9. Each row of the data flow program comprises destination information, instruction information and copy presence/absence information. As shown in FIG. 9, the information fetching portion 8 reads destination information, instruction information and copy presence/absence information of the data flow program by addressing based on the destination information of an input data packet, stores the destination information and the instruction information in the destination field and the instruction field of the data packet and outputs the data packet.
The data pair generating portion 2 queues data packets output from the program storing portion 1. More specifically, the data pair generating portion 2 detects two different data packets having the same destination information, stores the operand data (the contents of the data 1 field in FIG. 8) of one of the data packets in the data 2 field of the other data packet and outputs the other data packet.
The operation processing portion 3 performs an operation processing with respect to a data packet output from the data pair generating portion 2 based on the instruction information of the data packet, stores the result of the operation processing in the data 1 field of the data packet and outputs the data packet to the program storing portion 1.
As a data packet continues to circulate through the program storing portion 1, the data pair generating portion 2, the operation processing portion 3, the program storing portion 1, . . . , the operation processing proceeds in accordance with the data flow program stored in the program storing portion 1.
FIG. 10 is a diagram showing one example of a data flow program. FIG. 11 is a diagram showing a part of the storage contents of the program storing portion 1 corresponding to the data flow program shown in FIG. 10.
In FIG. 10, N1-N9 are nodes. D1-D9 denote the node numbers of the nodes N1-N9, respectively and op1-op9 denote the operation codes of the nodes N1-N9, respectively. The node numbers D1-D9 correspond to destination information and op1-op9 correspond to instruction information.
For example, the operation result at the node N1 is referred to by the nodes N2, N3 and N4. In this case, a copy process is carried out at the program storing portion 1.
The copy process will be described. The contents of a row addressed based on the destination information of an input data packet is read from the data flow program. At this time, when the copy presence/absence information indicates "absence", the data packet is output with the contents of the destination field and the instruction field updated to complete the processing.
Conversely, when the copy presence/absence information indicates "presence", the data packet is output with the contents of the destination field and the instruction field updated, and destination information, instruction information and copy presence/absence information stored in the subsequent row are read out. When the copy presence/absence information read out from the subsequent row indicates "absence", the same data as that of the input data packet is stored in the data 1 field of another data packet and the destination information and the instruction information which have been just read out are respectively stored in the destination field and the instruction field of said another data packet, which packet is output. If the copy presence/absence information read out from the subsequent row indicates "presence", the same copy processing will be further repeated.
FIG. 12 is a schematic diagram showing an execution state of the data flow program of FIG. 10.
At time T, the data latch 9c in the proceeding stage to the information fetching portion 8 holds a data packet including destination information D1. The latches 9b and 9a in further proceeding stage hold data packets including destination information D7 and destination information D8, respectively. Such is a state just before the data packet including the destination information D1 is input to the information fetching portion 8.
At time T+.DELTA.t, the information fetching portion 8 receives the data packet including the destination information D1, at which a processing is carried out with respect to the data packet. Herein .DELTA.t represents a time period required for the information fetching portion 8 to read destination information, instruction information and copy presence/absence information in a subsequent row by addressing based on the destination information of an input data packet received, to store said destination information and said instruction information in the destination field anti the instruction field of the input data packet and to output said data packet. The data latches 9a-9c and 11a-11d respectively constituting the input buffer 10 and the output buffer 11 transfer data packets held therein to the data latches in the succeeding stage at a time interval of .DELTA.t. At time T+.DELTA.t, the data packet including the destination information D7 and the data packet including the destination information D8 are transferred to the data latches 9c and 9b in their subsequent stages, respectively.
At time T+2.multidot..DELTA.t, the information fetching portion 8 outputs a data packet including the destination information D2 and a data packet including the destination information D3 to the data latches 11a and 11c, respectively, as a result of the processing with respect to the data packet including the destination information D1 in accordance with the data flow program shown in FIGS. 10 and 11. With only the two data latches 11a and 11c connected to the output ports, the information fetching portion 8 is not allowed to output a data packet including the destination information D4. Therefore, the information fetching portion 8 successively performs the processing with respect to the data packet including the destination information D1. As a result, the information fetching portion 8 receives no packet including the destination D7. In other words, at time T+2.multidot..DELTA.t, the data packet including the destination information D7 and the data packet including the destination information D8 are held in the same data latches 9c and 9d as those at time T+.DELTA.t. At this time, another packet is transferred to the data latch 9a.
At time T+3.multidot..DELTA.t, the information fetching portion 8 outputs a data packet including the destination information D4 to the data latch 11a as a result of the processing with respect to the data packet including the destination information D1 performed at time T+2.multidot..DELTA.t in accordance with the data flow program shown in FIGS. 10 and 11. At this time, the information fetching portion 8 performs a processing with respect to a data packet including the destination information D7, while the data packet including the destination information D8 and the subsequent data packet are transferred to the data latches 9c and 9d in their subsequent stages, respectively.
In the above-described execution control system for copy processing of data packets, when a data packet having three or more destinations is input as is done at time T+.DELTA.t and time T+2.multidot..DELTA.t of FIG. 12 (when two or more copy processings are carried out), a data packet in each data latch of the input buffer 10 is not allowed to proceed to the subsequent stage but to stay.
When data packets are input to the information fetching portion 8 at a low flow rate, even if a data packet temporarily stays in the input buffer 10 of the program storing portion 1, the stay will be eliminated in due course. However, when data packets are input to the information fetching portion 8 at a high rate and the data flow program requires copy processing to be performed many times, data packets exceeding the allowable amount might stay in the input buffer 10 of the program storing portion 1 to stop the data driven type information processing device.
The following method is presented to prevent data packets from staying in the input buffer 10 of the program storing portion 1.
As shown in FIG. 13, the data flow program of FIG. 10 is changed such that each node has less than 3 destinations. FIG. 14 is a diagram showing a part of the storage contents of the program storing portion 1 corresponding to the data flow program of FIG. 13.
As shown in FIGS. 13 and 14, a node N10 is provided between a node N1 and nodes N3 and N4, for example. The operation code nop (no operation) of the node N10 indicates that an input data packet is output without being subjected to any operation processing. The provision of the node N10 changes the node N1 having three destinations in FIG. 10 to have two destinations in FIG. 13.
FIG. 15 is a schematic diagram showing an execution state of the data flow program of FIG. 13.
The states at times T and T+.DELTA.t are the same as those shown in FIG. 12. At time T+2.multidot..DELTA.t, the information fetching porion 8 outputs a data packet having the destination information D2 and a data packet having the destination information D10 to the data latches 11a and 11c, respectively, as a result of the processing with respect to the data packet including the destination information D1 in accordance with the data flow program shown in FIGS. 13 and 14. At this time, the operation fetching portion 8 performs a processing with respect to the data packet including the destination information D7, while the data packet including the destination information D8 is transferred to the data latch 9c.
At time T+3.multidot..DELTA.t, the information fetching portion 8 outputs a data packet including the destination information D9 to the data latch 11a as a result of the processing with respect to the data packet including the destination information D7 in accordance with the data flow program shown in FIGS. 13 and 14.
Since the data flow program shown in FIG. 13 is changed not to generate a data packet having three or more destinations, there occurs no stay of data packets in the input buffer 10 of the program storing portion 1.
According to the above-described method, however, addition of nodes having an operation code nop increases the amount of object code of the data flow program, thereby increasing an execution time period for executing these nodes during an operation processing.